import java.util.Arrays;

/**
 * @program: data_structures_algorithms
 * @description: 插入排序
 * @author: lld
 * @create: 2020/08/28 18:01
 **/
public class InsertSort {
    public static void main(String[] args) {
        int[] array1 = {1, -1, 3, 2, -6};
        System.out.println("原数组：" + Arrays.toString(array1));
//        sort(array1);
        sort1(array1);
        //测试执行效率
//        int[] bigArray1=new int[50000];
//        for(int i=0;i<bigArray1.length;i++){
//            bigArray1[i]=(int)(Math.random()*1000000);
//        }
//        long start = System.currentTimeMillis();
//        sort(bigArray1);
//        long end = System.currentTimeMillis();
//        System.out.println("50000个数据排序时间(毫秒):"+(end-start));//370
    }

    public static void sort(int[] array1) {
        for (int i = 1; i < array1.length; i++) {
            int insertVal = array1[i];//待插入的数
            int insertIndex = i - 1;//待插入的前一个数的索引,也就是有序数组的最后一个
            /*insertIndex>=0
            insertVal<array1[insertIndex] 待插入的数<前一个数
            **/
            while (insertIndex>=0&&insertVal<array1[insertIndex]){
                array1[insertIndex+1]=array1[insertIndex];//{1,-1,3,2,-6}=>{1,1,3,2,-6},当前待插入的数保存在insertVal
                insertIndex--;
            }
            array1[insertIndex+1]=insertVal;
            System.out.println("第" + i + "次排序:" + Arrays.toString(array1));
        }
    }
    public static void sort1(int[] array1) {
        for (int i = 1; i < array1.length; i++) {
            int insertVal = array1[i];//待插入的数
            int j;
            for( j=i;(j>0)&&(insertVal<array1[j-1]);j--){
                array1[j]=array1[j-1];
            }
            array1[j]=insertVal;
            System.out.println("第" + i + "次排序:" + Arrays.toString(array1));
        }
    }
}
